import java.util.*;

class MaxRectangle {
    // 字典树
    class Trie {
        Trie[] children;
        boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }
    }

    Trie root;
    int maxArea;
    int maxLength;
    Map<Integer, Set<String>> map;
    List<String> ans;

    private void insert(String s) {
        Trie cur = root;
        for (char c : s.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new Trie();
            }
            cur = cur.children[c - 'a'];
        }
        cur.isEnd = true;
    }

    public String[] maxRectangle(String[] words) {
        root = new Trie();
        maxArea = 0;
        maxLength = 0;
        map = new HashMap<>();

        for (String s : words) {
            insert(s);
            maxLength = Math.max(maxLength, s.length()); // 记录最长字符串长度
            Set<String> set = map.getOrDefault(s.length(), new HashSet<>());
            set.add(s);
            map.put(s.length(), set);
        }

        // For each possible word length, perform DFS
        for (int key : map.keySet()) {
            List<String> path = new ArrayList<>(); // Create new list for each key
            dfs(map.get(key), path, key);
        }

        return ans == null ? new String[0] : ans.toArray(new String[ans.size()]);
    }

    private void dfs(Set<String> set, List<String> path, int length) {
        // Pruning: if current potential area can't beat maxArea, return
        if (length * maxLength <= maxArea) {
            return;
        }

        // Check current path validity
        boolean[] validation = isValid(path);
        boolean isValidPrefix = validation[0];
        boolean isCompleteWord = validation[1];

        // If current path is invalid as prefix, prune this branch
        if (!isValidPrefix) {
            return;
        }

        // If we have a complete valid rectangle, update result
        if (isCompleteWord && !path.isEmpty()) {
            int area = path.size() * length;
            if (area > maxArea) {
                maxArea = area;
                ans = new ArrayList<>(path);
            }
        }

        // Continue building the rectangle
        if (path.size() < maxLength) {
            for (String s : set) {
                path.add(s);
                dfs(set, path, length);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 验证当前路径是否有效
     * 
     * @return boolean[2]: [0]表示是否是有效的前缀，[1]表示是否所有列都是完整单词
     */
    public boolean[] isValid(List<String> input) {
        // 空路径被认为是有效的
        if (input.isEmpty()) {
            return new boolean[] { true, true };
        }

        boolean allLeaf = true;
        int m = input.size();
        int n = input.get(0).length();

        for (int j = 0; j < n; j++) {
            // 按列来看单词是否在字典树
            Trie node = root;
            for (int i = 0; i < m; i++) {
                int c = input.get(i).charAt(j) - 'a';
                if (node.children[c] == null) {
                    return new boolean[] { false, false };
                }
                node = node.children[c];
            }
            if (!node.isEnd) {
                allLeaf = false;
            }
        }
        return new boolean[] { true, allLeaf };
    }

    public static void main(String[] args) {
        String[] words = new String[] { "this", "real", "hard", "trh", "hea", "iar", "sld" };
        MaxRectangle maxRectangle = new MaxRectangle();
        String[] res = maxRectangle.maxRectangle(words);
        System.out.println(Arrays.toString(res));
        
        // Test the large case
        String[] largeWords = new String[] {"cwsmqtaausjakauhujlpgjwpapsyunylpivxzbbdkxfxmeoypt", "n", "gd", "ib", "zj", "uw", "fg", "nr", "qp", "fb", "vq", "gz", "un", "tl", "gn", "bshvfxaadfogxjjgmjuwijdcpnluaztzyyzhwkkpsznvilhhcc", "bg", "zb", "qc", "rs", "jj", "khkxfuyqkfmrmqnxkbokatfkaplbdallpjdryysfrqbjuzatqf", "ju", "iq", "hx", "zkvygirllpckgxwctgiyzbcuffnqolmbghvzaejzpqckrmjzwu", "aj", "mn", "ad", "oa", "kr", "bs", "mh", "pe", "ce", "xn", "jc", "ha", "zk", "gf", "xw", "ku", "ll", "fn", "ii", "gw", "yu", "up", "xh", "lo", "bsjsjppqxtqwrsxeyamophripgayjuzupkbqmkqmeqjkilcubh", "ne", "z", "bv", "ja", "rv", "lh", "dq", "ve", "jk", "qu", "zw", "lw", "aw", "rm", "bb", "xi", "rq", "zt", "js", "xu", "kw", "ro", "sf", "by", "gb", "mu", "jz", "gi", "boquvjhgadilhsbxhjtlmmutmnuttxugmhafppojfgbxghabuy", "yp", "lg", "cu", "ct", "mw", "xk", "sl", "zf", "eh", "so", "sp", "kp", "qz", "ty", "dy", "dz", "jt", "ey", "yt", "ih", "iwdggfxtdgklqpxdsarqexjbgepkdbkmnvdzbmdudhpjbngdxp", "hf", "mx", "uouzqwjkwdzvqfdhzpfvzpeajfkvtxdkcrwhvbqbhlqshyaybh", "ef", "ir", "adktqiniltegtvohcunbbxwzpmypkgodihutzinwiufbegevqc", "bh", "dm", "fk", "uk", "ae", "nm", "qk", "toilgaddlgxypkpvfpkctfyiudjcbjpfedgjmvsfrenrvroxdi", "ao", "bthhjsqqrqjubfivllsydjmmwpjlymynhqpofwlayzxwksicuu", "tjecqwbnfgnpqaqkfkyailypqaubuqwcmhjimphfazbroagzyb", "xr", "gs", "r", "rn", "oiikbjjpjngxprbkkerocamygvghxwxboyxafyumexsyycsfcu", "sm", "ij", "fj", "ta", "fe", "ox", "rz", "cg", "vv", "cz", "pv", "uj", "em", "rl", "uv", "vy", "yzvaqlpeuafqfrgdxnsrtsizleobksnijtrvhcvjxzrvvwhlzj", "wl", "nu", "io", "bm", "lmkrzmfvhaidusnztyjdxchgthqabzerrnbysboyauwuiqgnrj", "pp", "whqplhrluofemarlwgvonyoivmkhaaugqfgifdpxyufaiikqaq", "cb", "ri", "ym", "lu", "pcgamtwwpqyokvdzimjmeompemhxewwjjmhywfinsjmmrrmnbi", "ncqfjjreumidraarkycprwzkdudpzkecyzkcyaxuuvhnfjfrtn", "to", "mr", "bycjuhplzcjrscepphwcccalrosgonyzgexlojtshileqceyyt", "sn", "xp", "kf", "ul", "pb", "iv", "ea", "ap", "su", "th", "kg", "ysukcysqdilqemxikiqynsifdeiblrvznedfrlalmzczqywmqv", "lj", "xz", "ra", "fo", "iy", "mm", "zu", "pwjpjxirlqswexleoeotuqudzpseowuqjihmbfmlepgquixppa", "ya", "dg", "lktvueuukxahguvplyocaoyqspfqvwgmrznztlaefxspicorpe", "dw", "nbznkghfiljhsvuiznshnzwkpuukikbzeyeuqrmthdrkncmjiv", "vr", "jh", "ly", "co", "bt", "bl", "wv", "er", "wd", "ye", "mi", "ny", "hy", "nz", "ip", "wk", "hn", "asaplbgmfnfaycpddojdcliwvuylsoiefsmkaazjzherdjbxus", "tr", "st", "sa", "ke", "ee", "wh", "px", "ws", "ng", "qflxhbcepgukmlsyeneiuvagdnpyallkepgniutddpkrhpsecr", "jl", "cy", "av", "pt", "hj", "rk", "kd", "gx", "kk", "esfpdztmjtnbglsslxvwkyrkrhwybbwhataverbwkqghupczvo", "qv", "vo", "xc", "gr", "ml", "uf", "hq", "hdhqghtxfhmrmdpmzdaylngtgoqznqaztchfanvumqdraxeixq", "ak", "bz", "yk", "rpuwhkpibuypilyabjnqnekaptlypkgxozbjvozptessyyvicr", "lb", "yx", "gqovsmbldqwfyroyyweeukudtxikqatyauguorjvgzrppjydtl", "da", "dn", "du", "atsbxpvmjtcernkghoznhgvslekssoigjnneooveoruaqgyytn", "qg", "li", "py", "tw", "dj", "if", "ns", "eq", "ni", "si", "tx", "as", "at", "sy", "jx", "in", "mp", "uzlwwhtvmfilekqrliftjgnqxnjrnsltcywobftyfsaxiazlqz", "xf", "zsnuzoiqeezwujyngvppjofnksppakejmlgrbknlpqhckeungv", "ux", "uu", "jhxynhixxbrrkufmtxdjikkevrvntsgngttgudondepizpnikd", "rf", "pj", "rc", "m", "nh", "zs", "am", "jd", "wg", "ms", "bw", "kx", "ka", "yn", "tg", "gj", "fi", "krstgziiqabggvvufvuszmsyiiaxdwzawrbozbrvafuefoglqs", "te", "aa", "jg", "nf", "yw", "yq", "zm", "nt", "en", "rucggdxdkynxyvkhvbyanotbtqbfzpzyavzbkahjgpfjllzyef", "d", "kj", "elhfspkxdxqnpmpkdcgmosmglcdcgvqwbrxfzmlaurtvaythjk", "kq", "vc", "ho", "wj", "xq", "ic", "ev", "wy", "tc", "fooqakmfhzcsotjjkozdbijsoetdwqiktlisrstduwlnmksslh", "uz", "el", "hw", "gp", "np", "ph", "be", "dd", "mo", "lc", "va", "tq", "vl", "ln", "az", "tz", "dkidytafkhhlbmdhzkgqmcvctbafroiitafzwoyoohkzhhikie", "v", "xx", "jf", "rfzndcdrshuillnjwrttsorsjqemazazpeifkoecqkvewbtbth", "us", "cj", "mv", "fl", "qj", "ck", "bk", "s", "ls", "wo", "htfmmbnstvtfixgolzkebgjxdtimcvnjiddkzokkuoebptxhuo", "rw", "mz", "vu", "it", "wn", "hz", "xmgsracbzttbwqpiwpflflhvmcjedvnrwxxptjbifdstrpipwv", "wm", "yb", "tu", "cd", "ds", "bu", "db", "gadtwqkazgwellbnmhirhcknahqxeiqgmdgumtujnkedlufyjs", "vlmqrilyscywjlytqzvogakjypnksnhhmovdgikqcbjtfescug", "t", "nc", "yr", "ch", "i", "rd", "eb", "pq", "xy", "do", "hu", "c", "kjxhwupoxpqtcgafzyxmceippseyqwowdgxacppmwljsreiqwk", "k", "vb", "df", "sq", "ou", "pc", "tn", "yg", "eg", "wt", "je", "mt", "vi", "ob", "wu", "os", "atlqerdjdszzmyqwutkcixujbnymgpjrssmadscnxokzbvalge", "ac", "xo", "cm", "za", "im", "gu", "jnwpdxbterxxgqsifspvhtjkrrjrzsbkmkjpbxgtvxghaeovem", "nb", "hp", "fhguuzpuricbknarvfvuuaiqjuoneprtedxhokkoomnpyzrffk", "ze", "oc", "xb", "o", "hc", "yy", "qw", "hv", "sc", "bx", "ci", "ax", "sx", "uh", "au", "ut", "ld", "y", "x", "eu", "kn", "go", "pz", "hk", "nl", "po", "mc", "ivhfelbyrrdjtxtdilqhhxpwyeuusgrrewzggafnkwqxdhwqnp", "lfprlmqoqyaidlggysrjvraskrfaihsvnlojvcxdkxwqsujmmc", "b", "aq", "ti", "ar", "vqtrekspbphuhdjmvbrbrsbjnwxwefsaujonueezvgsgwshctk", "jdjikdnrfuynqdenupurxwwxvdrenuwznduourgrkfzwxsucob", "p", "hjzxxhlvpmrdcgomiaydnmmkqyrawxhczldrdmqhzzmslpfzvz", "dr", "vs", "cv", "zg", "on", "yf", "pa", "gupimkaxzmfktkzdctinmhlimdfcxhipsmdoluodlbvkyhcmki", "flbabfhawdaqlwvpcstuikgcjkdqknfcmopnqtvpussgflmeqb", "f", "oy", "sr", "reoukvhpfgzkdsimjuifwmyrybmwmuoavkfdsijwlugjhyfimd", "xsqxmaanlrljzihrgpguewkbqksrzhgkonlbfpmudiubernymq", "kveomwtmyfyfnucdcphwqfmmmifhibnbogbwzazulbqbstbrzk", "h", "or", "tk", "xm", "ex", "og", "lt", "q", "e", "ykypmlotoztrgvwnpxuzhvawbkterpdbjcmtbamvgeahgzdgsq", "xa", "na", "zp", "qa", "ru", "sd", "gv", "zupodigekkqqpzxzgqvzziejimhrbokysmuhsafjpjbwktnuhl", "jjutatmjaydqkppqzmlvpgqpuowfkdqblyipivdvmzjrtskdlu", "iz", "yd", "sk", "vk", "rx", "hg", "gk", "hr", "ekciqajslpdscierruoyuguajljprqvtknplayirfsdjqfpidw", "om", "ub", "xd", "km", "ez", "he", "dx", "ig", "id", "pd", "qhegnofrraudcxwzdfxmheaersybvxpgocgsazukleuvafpmuj", "wa", "qt", "cw", "no", "lp", "wb", "ql", "yzkahsewrhfriyjbbuwnaaglygppsstpqfgifsfeakptocpsfj", "wi", "iu", "bo", "ge", "gh", "cf", "wf", "qemoqpltvoneqrgrmtouakbuonlcnfmfmheuicsasqwhmorwvf", "gm", "ie", "rh", "a", "pi", "rkilafbvqwenffovvgebfpnqdtqjxfqtmygaimsrxratvuqqxk", "nd", "pu", "vz", "uo", "rb", "fs", "yoprekcfrmetsdrkjinmhhdpkmcqmvtgkaqknvbpcbhgmsqehe", "opekcclbtawwhvemtmstzalhfkjhxbavgagjmlgwhqktcoosst", "bf", "wzsymzwxkbkgjxziqhxezkfyfmlmtcaphqxmfdlucocftlgkdj", "ud", "fq", "ur", "vd", "nq", "nzavtdsdxafxrihxsuaxnkcslohgevipbqivtpmiipaprvukfp", "fr", "bi", "obcrtojfysapvcpmfpchrypkvcwbfszaoivkbaoruftxblklmj", "zd", "oe", "nw", "dh", "yc", "jo", "vkgsqujvizliryrtqbugstjizernuxctirsvcfeqdkvlwpvsad", "jr", "br", "samdncvzklkbpqpkitzikypiiumlahfwsjacywxxidckgqnfgc", "ok", "fv", "rj", "ed", "qx", "oz", "bq", "fhlpatrkdqzpvcedjrjdutdcurwiencuimpkkjtcjwkoqtlpep", "uc", "tb", "ts", "es", "vg", "lx", "lv", "oi", "tt", "zr", "zo", "eriudaxijfznacglrhtxyyhkdhqzqqpcnofyrsddmioknzlerm", "jm", "jb", "od", "hm", "qy", "klmzkhdjqkvibelzkgzjdxzqeqznfpmerbezfhofbpsxuxqzrw", "ua", "vm", "mk", "hb", "zy", "pm", "iw", "dc", "la", "vp", "zl", "lqkylbwdmirzskccrhfwspqrpqbwedwgrjixgyiqtelguguepv", "zxhaiovtaskhvywxxxsvkwqujfmknklpondzwovuhwnszwkrvn", "jv", "fm", "ps", "wz", "jq", "sv", "vh", "nv", "pqovwnffwqsgdhnsckeqmbuhdlqwpkglwqbpbsrkxpfbanitsm", "ia", "jy", "vw", "lz", "nj", "uq", "hs", "wp", "qf", "se", "qe", "ab", "yi", "hhblsevefjnqeekzdyjuvubhifusxmqqngpcssobiabmjevvkp", "dp", "dfedkaivixvydogxxiqftbpzjesmjtilwitumfpxrjpmllymwe", "vf", "ol", "qn", "sw", "bc", "oq", "ky", "il", "tv", "xj", "zz", "eo", "vt", "bd", "md", "xg", "copaksgibhlhkpqxsugbseomulcglhkvgidgecmnemtfqcxcqb", "zq", "fp", "ff", "yv", "qo", "tm", "kv", "eqmjuybpsfxmbypqeovnmuhqsslparumvkvkrzkgomvgoanalt", "yj", "et", "adzxwpqbkythwjrjeqnjxtfiviyscvbymxquwhnkmjbwocxkzu", "pr", "lm", "lf", "ue", "xe", "lq", "kb", "kl", "ba", "cc", "nk", "nx", "sz", "jn", "ei", "nn", "uy", "an", "hi", "yz", "fa", "zi", "xt", "ji", "yh", "xl", "qm", "cr", "yl", "mq", "rt", "pl", "cp", "cs", "fz", "ug", "lr", "zikimyhqdalrwsxgagetoaofqlvmjlomwpkrnzurpmswuylhaq", "dqkswyrkfhjmezwxqvqwkbqjgqjfnwmmxrbfglmkmjbdzuzcsa", "oo", "lk", "tf", "pg", "cl", "yo", "ww", "vj", "u", "le", "ca", "kh", "gg", "mvgkxfembpprqvyantbskhbycclvnwmeskguxlmeceqraqpbci", "gq", "qb", "jw", "kc", "ej", "bp", "qq", "ov", "fh", "we", "vn", "jp", "ah", "me", "fx", "cx", "l", "ko", "wr", "tj", "fdrgfycjxzruwaanmyhaohwlfypvmkpqxzknhbpwbnwyhghzls", "mg", "my", "ziuibvhguhwziomtxbleugfaigpgmduvhfdxbvvvgeoagxsllp", "ai", "tbqtjiwwqftmhwwvauzzicybdvulksastulcquuokpqerpgqje", "gc", "zv", "taxyfiiyapfnqaifvahxmsgcorihsildysshgbxucxmogouwtl", "tfgeigfqowcgnoxyutsnsrymkoshyeeuzvluujkuiotpjopqgj", "bycdykpmtsryetqzsblkjfzuxwczpthgyclhlxhcmpevnrnmhp", "dl", "qi", "oh", "ht", "wx", "is", "sg", "wq", "ix", "of", "pk", "sh", "zwbenudxmnnseibttpybkxmakarngnkoeqdeifaxvfebaospkx", "zc", "hd", "bj", "hh", "vtzizanfmdkxklnuxloiqvsqplivyyvxvcpnucyoxedlacatwe", "gy", "ot", "oj", "fy", "pn", "mj", "dk", "vx", "fc", "pw", "kz", "ss", "ys", "ow", "ec", "al", "cq", "xv", "de", "zh", "w", "zn", "mb", "ay", "ek", "td", "cbnvjoixfeuupomhqjjktmfmfaawxkrveqvpvjkrdlptyellac", "kt", "qh", "fd", "ft", "ma", "qd", "dt", "wc", "zx", "szsuhmftaarehqcnsmtxnciptadokmohhguizcbxmuihxajnou", "rg", "ew", "qr", "rr", "ndqobdpgnjahrnaorbgrubqxpgiabnxwkymjvpgezlvsnvyxpe", "re", "tp", "ag", "ki", "pf", "gl", "ks", "fw", "gt", "ep", "j", "ga", "tvberqlfknpumimdglrjhoaocuyabqtznoewsderntuvdcpymd", "swbdzkzikrulrmxpiaukijfxlvrxmwdojsudqftfzlwehkeddd", "rp", "sb", "di", "um", "fu", "hl", "djgbkaciyeracnpljhpqhjbpdlqcdfhovlhaignnaihbfuiskr", "dv", "op", "g", "ui", "ry", "sj", "ik", "bn", "af", "mf", "cn", "xs", "qs"};
        MaxRectangle maxRectangle2 = new MaxRectangle();
        String[] res2 = maxRectangle2.maxRectangle(largeWords);
        System.out.println("Large test case result length: " + res2.length);
    }
}